from typing import List


class Solution:
    """
    此题题干，与动态规划有些相似
    将硬币从小到大排序。则：
    cc(coins,amount)=
    max_if_exist(
    cc(coins,amount-coins[-1])+1,
    cc(coins[:-1],amount-coins[-2])+1,
    ...
    cc(coins[:1],amount-counts[0])+1
    )
    换言之，如果从大到小排序，则
    res=max_if_exist(
    cc(coins,amount-coins[0])+1,
    cc(coins[1:],amount-coins[1])+1,
    ...
    cc(coins[-1:],amount-coins[-1])+1
    )
    
    """
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort(reverse=True)
        def cc(coins:List[int],amount:int)->int:
            if amount==0:
                return 0
            if amount<0:
                return -1
            
            # 贪心算法，但此法不一定求得最优解
            # 如coins=5，25，40，amount=50
            # 最优解是25*2，而不是40+5*2。考虑使用map分别记录最小次数
            for i,coin in enumerate(coins):
                res=cc(coins[i:],amount-coin) 
                if res!=-1:
                    print(coin)
                    return res+1
            return -1

        return cc(coins,amount)

if __name__=='__main__':
    coins=[186,419,83,408]
    amount=6249
    s=Solution()
    res=s.coinChange(coins,amount)
    print(res)